[2017_HackCon] [CRYPTO] RSA-2¶
문제내용¶
n = 109676931776753394141394564514720734236796584022842820507613945978304098920529412415619708851314423671483225500317195833435789174491417871864260375066278885574232653256425434296113773973874542733322600365156233965235292281146938652303374751525426102732530711430473466903656428846184387282528950095967567885381
e = 49446678600051379228760906286031155509742239832659705731559249988210578539211813543612425990507831160407165259046991194935262200565953842567148786053040450198919753834397378188932524599840027093290217612285214105791999673535556558448523448336314401414644879827127064929878383237432895170442176211946286617205
c = 103280644092615059984518332609100925251130437801342718478803923990158474621180283788652329522078935869010936203566024336697568861166241737937884153980866061431062015970439320809653170936674539901900312536610219900459284854811622720209705994060764318380465515920139663572083312965314519159261624303103692125635
문제 풀이¶
n과 e로 p, q를 구하는 함수가 있다. 가져다 쓰자.
sage: def factor_rsa_wiener(N, e):
"""Wiener's attack: Factorize the RSA modulus N given the public exponents
e when d is small.
Source: https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf
CTF: BKP CTF 2016 Bob's Hat
"""
N = Integer(N)
e = Integer(e)
cf = (e / N).continued_fraction().convergents()
for f in cf:
k = f.numer()
d = f.denom()
if k == 0:
continue
phi_N = ((e * d) - 1) / k
b = -(N - phi_N + 1)
dis = b ^ 2 - 4 * N
if dis.sign() == 1:
dis_sqrt = sqrt(dis)
p = (-b + dis_sqrt) / 2
q = (-b - dis_sqrt) / 2
if p.is_integer() and q.is_integer() and (p * q) % N == 0:
p = p % N
q = q % N
if p > q:
return (p, q)
else:
return (q, p)
sage: p,q = factor_rsa_wiener(n, e)
sage: phi = (p-1)*(q-1)
sage: d = inverse_mod(e, phi)
sage: decrypted = Mod(c, n) ** d
sage: flag = hex(Integer(decrypted)).decode('hex')
sage: print(flag)